package com.zang.tree;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @author ZVerify
 * @since 2022/10/31 16:52
 * @see <a href="https://leetcode.cn/problems/path-sum-ii/">...</a>
 **/
public class 路径总和II {
    int sum = 0;
    ArrayList<List<Integer>> arrayList = new ArrayList<>();
    LinkedList<Integer> list = new LinkedList<>();

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        dfs(root,targetSum);
        return arrayList;
    }

    private void dfs(TreeNode root, int targetSum) {

        if (root==null) {
            return ;
        }
        // 中序遍历
        // 计算当前节点值相加是否等于要找的值
        sum+=root.val;
        list.addLast(root.val);
        if (sum==targetSum &&root.left==null && root.right==null) {
            arrayList.add(new ArrayList<>(list));
        }
        // 遍历左树
        dfs(root.left,targetSum);
        // 遍历右树
        dfs(root.right,targetSum);
        // 返回上一节点回溯删除当前的总和
        Integer integer = list.pollLast();
        if (integer!=null){
            sum-=integer;
        }
    }
}
